package leetcode.editor.day;

// 1582. 二进制矩阵中的特殊位置
// https://leetcode.cn/problems/special-positions-in-a-binary-matrix/
class SpecialPositionsInABinaryMatrix {
    public static void main(String[] args) {
        Solution solution = new SpecialPositionsInABinaryMatrix().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        // 暴力
        // 时间复杂度O(n * m)
        /*public int numSpecial(int[][] mat) {
            int ans = 0;
            for (int i = 0; i < mat.length; i++) {
                for (int j = 0; j < mat[i].length; j++) {
                    if (mat[i][j] == 1 && isValid(mat, i, j)) ans++;
                }
            }
            return ans;
        }

        private boolean isValid(int[][] mat, int i, int j) {
            for (int k = 0; k < mat.length; k++) {
                if (k != i && mat[k][j] == 1) return false;
            }

            for (int k = 0; k < mat[0].length; k++) {
                if (k != j && mat[i][k] == 1) return false;
            }

            return true;
        }
*/

        // 使用第一行来标记下边每一列的1个数
        // https://leetcode.cn/problems/special-positions-in-a-binary-matrix/solution/er-jin-zhi-ju-zhen-zhong-de-te-shu-wei-z-kan4/
        // 这方法是说先统计每一行的1的频次，然后直接在第一行对应列加上这个频次。
        // 如果当前行就是第一行，我们再减个一，以免[1,0,0]变成[2,0,0]这种情况。最后得到的第一行的1的频次即为所求。
        public int numSpecial(int[][] mat) {
            int m = mat.length, n = mat[0].length;
            for (int i = 0; i < m; i++) {
                int cnt = 0;
                // 记录这一列1的个数
                for (int j = 0; j < n; j++) {
                    if (mat[i][j] == 1) cnt++;
                }

                // 如果为第一行，减一
                if (i == 0) cnt--;

                if (cnt > 0) {
                    for (int j = 0; j < n; j++) {
                        if (mat[i][j] == 1) {
                            mat[0][j] += cnt;
                        }
                    }
                }


            }

            // 统计1的个数
            int ans = 0;
            for (int j = 0; j < n; j++) {
                if (mat[0][j] == 1) ans++;
            }
            return ans;
        }

    }
//leetcode submit region end(Prohibit modification and deletion)

}
